'''
https://leetcode.cn/problems/minimum-score-triangulation-of-polygon/description/

由于划分的三角形，不能穿过，即两个三角形不能重叠
所以相邻的两个边一定是在一个三角形内的

枚举0和n-1作为三角形的底
在[1,n-2] 范围内枚举顶点
比如 m
    这个可能的答案就是v[0] * v[n-1] * m + （在[0, m] 和 [m, n-1] 范围内继续递归枚举）的结果
'''
from functools import cache
from typing import List


class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        INF = 1 << 32 - 1
        @cache
        def f(i, j):
            if i + 1 == j:   # 这个区间不足3个点
                return 0
            res = INF
            a = values[i]
            b = values[j]
            for m in range(i + 1, j):
                c = values[m]
                res = min(res, a*b*c + f(i, m) + f(m, j))
            return res
        return f(0, len(values) - 1)

    def minScoreTriangulation2(self, values: List[int]) -> int:
        INF = 1 << 32 - 1
        n = len(values)
        dp = [[INF] * n for _ in range(n)]
        # 第一维度依赖后边，第二维度依赖前边
        # 普遍位置依赖当前行左边多少列，下边多少行当前列   从下往上，从左往右
        # 初始位置 i,i+1 = 0
        # i<=j 只填上三角
        for i in range(n - 1):
            dp[i][i] = 0
            dp[i][i+1] = 0
        dp[-1][-1] = 0
        for i in range(n - 2, -1, -1):
            for j in range(i + 2, n):
                a = values[i]
                b = values[j]
                res = INF
                for m in range(i + 1, j):
                    c = values[m]
                    res = min(res, a*b*c + dp[i][m] + dp[m][j])
                dp[i][j] = res
        return dp[0][n - 1]
